package com.fengdi.book.hard;

import com.fengdi.publicObject.ListNode;
import com.fengdi.publicObject.Node;

import javax.security.auth.login.CredentialNotFoundException;
import java.sql.Array;
import java.util.ArrayList;

public class LinkList {
    public static class MergeKLists {
        public ListNode mergeKLists(ListNode[] lists) {
            if(lists.length == 0 || lists.length == 1) return lists.length == 0 ? null : lists[0];
            for(int i = 1; i < lists.length; i++) {
                this.merge(lists, i);
            }
            return lists[lists.length - 1];
        }

        private void merge(ListNode[] lists, int index) {
            ListNode list1 = lists[index - 1];
            ListNode list2 = lists[index];
            ListNode result = new ListNode();
            ListNode preNode = result;
            while (list1 != null && list2 != null) {
                if(list1.val < list2.val) {
                    preNode.next = list1;
                    list1 = list1.next;
                }else {
                    preNode.next = list2;
                    list2 = list2.next;
                }
                preNode = preNode.next;
            }

            while (list1 != null) {
                preNode.next = list1;
                list1 = list1.next;
                preNode = preNode.next;
            }

            while (list2 != null) {
                preNode.next = list2;
                list2 = list2.next;
                preNode = preNode.next;
            }
            lists[index] = result.next;
        }
    }

    public static class SortList {
        public ListNode sortList(ListNode head) {
            if (head == null || head.next == null) return head;
            return this.merge(head, null);
        }

        private ListNode merge(ListNode head, ListNode tail) {
            if(head.next == tail) {
                head.next = null;
                return head;
            }

            ListNode slow = head, fast = head;
            while (fast != tail && fast.next != tail) {
                fast = fast.next.next;
                slow = slow.next;
            }

            return mergeTowList(this.merge(head, slow), this.merge(slow, tail));
        }

        @SuppressWarnings("all")
        private ListNode mergeTowList(ListNode list1,  ListNode list2) {
            if (list1 == null) return list2;
            if (list2 == null) return list1;

            ListNode result = new ListNode();
            if (list1.val < list2.val) {
                list1.next = this.mergeTowList(list1.next, list2);
                result = list1;
            }else {
                list2.next = this.mergeTowList(list1, list2.next);
                result = list2;
            }

            return result;
        }
    }

    public static class CopyRandomList {
        public Node copyRandomList(Node head) {
            if (head == null) return null;

            // 创建新节点与旧节点的一一映射
            ArrayList<Node> list = new ArrayList<>();
            ArrayList<Node> help = new ArrayList<>();

            Node p = head;
            while (p != null) {
                list.add(p);
                help.add(new Node(p.val));
                p = p.next;
            }

            // 建立链表
            for(int i = 0; i < help.size() - 1; i++) {
                help.get(i).next = help.get(i + 1);
            }

            // 遍历原始链表建立随机链接
            for(int i = 0; i < list.size(); i++) {
                Node node = list.get(i);
                int randomIndex = list.indexOf(node.random);
                help.get(i).random = randomIndex == -1 ? null : help.get(randomIndex);
            }

            return help.getFirst();
        }
    }
}
